package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/range-sum-of-bst/">二叉搜索树的范围和(Range Sum of BST)</a>
 * <p>给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
 *                      10
 *                     /  \
 *                    5    15
 *                   / \     \
 *                  3   7     18
 *      输出：32
 *
 * 示例 2：
 *      输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
 *                       10
 *                     /    \
 *                    5     15
 *                   / \    / \
 *                  3   7  13  18
 *                 /   /
 *                1   6
 *      输出：23
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [1, 2 * 10^4] 内</li>
 *     <li>1 <= Node.val <= 10^5</li>
 *     <li>1 <= low <= high <= 10^5</li>
 *     <li>所有 Node.val 互不相同</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/17 15:36
 */
public class LC0938RangeSumOfBST_S {

    static class Solution {

        public int rangeSumBST(TreeNode root, int low, int high) {
            if (root == null) {
                return 0;
            }
            if (root.val < low) {
                return rangeSumBST(root.right, low, high);
            }
            if (root.val > high) {
                return rangeSumBST(root.left, low, high);
            }
            return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
        }

        public int rangeSumBST2(TreeNode root, int low, int high) {
            int ans = 0;
            if (root == null) {
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode currNode = queue.poll();
                if (currNode == null) {
                    continue;
                }
                if (currNode.val < low) {
                    queue.offer(currNode.right);
                } else if (currNode.val > high) {
                    queue.offer(currNode.left);
                } else {
                    ans += currNode.val;
                    queue.offer(currNode.right);
                    queue.offer(currNode.left);
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(10);
        root1.left = new TreeNode(5);
        root1.right = new TreeNode(15);
        root1.left.left = new TreeNode(3);
        root1.left.right = new TreeNode(7);
        root1.right.right = new TreeNode(18);

        TreeNode root2 = new TreeNode(15);
        root2.left = new TreeNode(9);
        root2.right = new TreeNode(21);
        root2.left.left = new TreeNode(7);
        root2.left.left.left = new TreeNode(5);
        root2.left.right = new TreeNode(13);
        root2.left.right.left = new TreeNode(11);
        root2.right.left = new TreeNode(19);
        root2.right.left.left = new TreeNode(17);
        root2.right.right = new TreeNode(23);

        Solution solution = new Solution();
        System.out.println(solution.rangeSumBST2(root1, 7, 15));
        System.out.println(solution.rangeSumBST2(root2, 19, 21));
    }
}
